/*
leetcode 2:两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
 

提示：
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零
 */

#include <iostream>
using namespace std;

// 定义链表节点结构
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy(0); // 创建一个哑节点，便于处理链表
        ListNode* current = &dummy; // 当前指针，用于构建结果链表
        int carry = 0; // 进位

        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            int sum = carry; // 当前位的总和，初始化为进位值

            if (l1 != nullptr) {
                sum += l1->val;
                l1 = l1->next;
            }

            if (l2 != nullptr) {
                sum += l2->val;
                l2 = l2->next;
            }

            carry = sum / 10; // 更新进位
            current->next = new ListNode(sum % 10); // 创建新节点
            current = current->next; // 移动指针到下一个节点
        }

        return dummy.next; // 返回结果链表，哑节点dummy -> 7 -> 0 -> 8 -> null，所以返回的是 dummy.next
    }
};

// 辅助函数：打印链表
void printLinkedList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

// 主函数
int main() {
    // 示例输入1: 2->4->3 (表示342)
    ListNode* l1 = new ListNode(2);
    l1->next = new ListNode(4);
    l1->next->next = new ListNode(3);

    // 示例输入2: 5->6->4 (表示465)
    ListNode* l2 = new ListNode(5);
    l2->next = new ListNode(6);
    l2->next->next = new ListNode(4);

    Solution solution;
    ListNode* result = solution.addTwoNumbers(l1, l2);

    // 输出结果
    cout << "Result: ";
    printLinkedList(result);

    return 0;
}

/*
示例输入
链表 l1: 2 -> 4 -> 3 和 l2: 5 -> 6 -> 4，对应的两个数字是 342 和 465。

逆序存储
链表 l1: 2 -> 4 -> 3 表示数字 342，因为 2 是个位，4 是十位，3 是百位。
链表 l2: 5 -> 6 -> 4 表示数字 465，同样 5 是个位，6 是十位，4 是百位。

初始化
carry = 0（进位初始为 0）
dummy 是一个哑节点，用于构建结果链表。
current 指向哑节点 dummy。

第一步：处理个位
l1.val = 2，l2.val = 5，carry = 0。
sum = 0 + 2 + 5 = 7。
当前位：7 % 10 = 7，进位：7 / 10 = 0。
新节点值为 7，添加到结果链表。
l1 移动到 4，l2 移动到 6。
结果链表：7 -> null

第二步：处理十位
l1.val = 4，l2.val = 6，carry = 0。
sum = 0 + 4 + 6 = 10。
当前位：10 % 10 = 0，进位：10 / 10 = 1。
新节点值为 0，添加到结果链表。
l1 移动到 3，l2 移动到 4。
结果链表：7 -> 0 -> null

第三步：处理百位
l1.val = 3，l2.val = 4，carry = 1。
sum = 1 + 3 + 4 = 8。
当前位：8 % 10 = 8，进位：8 / 10 = 0。
新节点值为 8，添加到结果链表。
l1 和 l2 均为空。

结果链表：7 -> 0 -> 8 -> null

循环终止
此时，l1 和 l2 均为空，且进位 carry = 0，循环终止。

最终结果
结果链表为 7 -> 0 -> 8，表示数字 807，即 342 + 465 = 807。
*/
